package leetcode

//https://leetcode.com/problems/find-the-duplicate-number/

/**
Given an sort.getArray nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2
Example 2:

Input: [3,1,3,4,2]
Output: 3
Note:

You must not modify the sort.getArray (assume the sort.getArray is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n^2).
There is only one duplicate number in the sort.getArray, but it could be repeated more than once.
 */
//二分查找的巧妙应用，因为无法修改数组，同时要求常数空间复杂度，明显就是要直接从原数组中直接找到这个重复的值，
//那么可以考虑二分法，利用中位数 n/2，然后遍历一遍数组，看比n/2大的数字的个数，如果大于n/2说明重复的数字在 n/2~n之间反之在前半段
//参考 http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/
fun main(args: Array<String>) {

}

//TODO
fun findDuplicate(nums: IntArray): Int {

    return 0
}